ABC126 D - Even Relation

解答

code: python

from collections import defaultdict

n = int(input())

d = defaultdict(list)

for u, v, w in uvw:

du.append((v, w))

dv.append((u, w))

# print(d)

# defaultdict(<class 'list'>, {1: (2, 2), 2: (1, 2), (3, 1), 3: (2, 1)})

# この問題の制約下では、塗り分け方が必ず1つは存在する

# 頂点iを何色で塗るか

ans = -1 * (n + 1)

# 頂点 1 は白で塗る

stack = 1, 0

while stack:

i, color = stack.pop()

ansi = color

for to, w in di:

# 既に塗っていたら

if ansto != -1:

continue

if w % 2 == 0:

stack.append(to, color)

# 辺の重みが奇数なら次は違う色で塗る

else:

stack.append(to, color ^ 1)

ans.pop(0)

for v in ans:

print(v)

テーマ

メモ